/// 公共数据结构
module factories.container;

import std.algorithm : swap;

/// 变长二维数组
struct MultiArray(T, uint N, uint M) {
	/// 索引：indices[i]表示id为i的流水线的data数组起始索引
	uint[N] indices;
	T[M] data;

	enum length = N;

	auto opIndex(size_t index) {
		if (index > N - 1)
			return null;

		return data[indices[index] .. index == N - 1 ? $: indices[index + 1]];
	}

	T as(T)(size_t index) => T(opIndex(index));
}

/// 转换为前缀和
void toPrefixSum(T)(ref T[] arr) {
	for (size_t i = 1; i < arr.length; i++)
		arr[i] += arr[i - 1];
}

unittest {
	int[3] arr = [1, 2, 3];
	int[] a = arr;
	toPrefixSum(a);
	assert(a == [1, 3, 6]);
}

/// 队列
struct Queue(T, size_t N = 16) {
	enum capacity = N;

	T[N] data;
	size_t head;
	size_t tail;

	void push(T value) {
		if (full)
			return;

		data[tail++] = value;
		tail %= N;
	}

	T pop() {
		auto value = data[head++];
		head %= N;
		return value;
	}

	@property {
		bool empty() const => head == tail;
		bool full() const => (tail + 1) % N == head;
		ref front() => data[head];
	}
}

unittest {
	Queue!int q;
	assert(q.empty);
	q.push(1);
	assert(!q.empty);
	q.push(2);
	assert(q.pop() == 1);
	assert(q.pop() == 2);
}

struct PriorityQueue(T, size_t N = 16) {
	enum capacity = N;
	T[N] data;
	size_t size;

	@property {
		bool empty() const => size == 0;
		bool full() const => size == N;

		ref front() => data[0];
	}

	bool push(T value) {
		if (size == N)
			return false;
		data[size] = value;
		for (size_t i = size; i;) {
			auto parent = (i - 1) / 2;
			if (data[i] >= data[parent])
				break;
			swap(data[i], data[parent]);
			i = parent;
		}
		size++;
		return true;
	}

	T pop()
	in (size, "Queue is empty") {
		auto value = data[0];
		data[0] = data[--size];
		for (size_t i;;) {
			auto left = 2 * i + 1;
			if (left >= size)
				break;
			auto right = 2 * (i + 1);
			auto next = i;
			if (data[left] < data[next])
				next = left;
			if (right < size && data[right] < data[next])
				next = right;
			if (next == i)
				break;
			swap(data[i], data[next]);
			i = next;
		}
		return value;
	}
}

unittest {
	PriorityQueue!int q;
	assert(q.empty);
	q.push(2);
	assert(q.front == 2);
	q.push(1);
	assert(q.pop() == 1);
	assert(q.pop() == 2);
	PriorityQueue!(int, 2) r;
	assert(r.push(1));
	assert(r.push(2));
	assert(!r.push(3));
}

struct Map(K, V, size_t N = 16) {
	static assert(!((N - 1) & N), "N must be a power of 2");
pure:
	struct Bucket {
	private pure nothrow @nogc @safe:
		size_t hash;
		K key;
		V val;

		@property bool empty() const => hash == Hash.empty;

		@property bool deleted() const => hash == Hash.deleted;

		@property bool filled() const => cast(ptrdiff_t)hash < 0;
	}

	private {
		Bucket[N] buckets;
		uint used;
		uint deleted;

		size_t calcHash(in K pkey) {
			// highest bit is set to distinguish empty/deleted from filled buckets
			const hash = cast(size_t)pkey;
			return mix(hash) | Hash.filled;
		}

		inout(Bucket)* findSlotInsert(size_t hash) inout {
			for (size_t i = hash & mask, j = 1;; ++j) {
				if (!buckets[i].filled)
					return &buckets[i];
				i = (i + j) & mask;
			}
		}

		inout(Bucket)* findSlotLookup(size_t hash, in K key) inout {
			size_t n;
			for (size_t i = hash & mask; n < buckets.length; ++n) {
				if (buckets[i].hash == hash && key == buckets[i].key)
					return &buckets[i];
				i = (i + 1) & mask;
			}
			return null;
		}
	}

	enum mask = N - 1;

	enum dim = buckets.length;

	@property @safe {
		uint length() const
		in (used >= deleted) => used - deleted;

		bool empty() const => length == 0;

		bool full() const => length == buckets.length;
	}

	bool set(in K key, V val) {
		if (length == N)
			return false;

		const keyHash = calcHash(key);
		if (auto p = findSlotLookup(keyHash, key)) {
			p.val = val;
			return true;
		}

		auto p = findSlotInsert(keyHash);
		if (p.deleted)
			--deleted;

		// check load factor and possibly grow
		else if (++used > dim)
			return false;

		p.hash = keyHash;
		p.key = key;
		p.val = val;
		return true;
	}

	bool remove(in K key) {
		if (!length)
			return false;

		const hash = calcHash(key);
		if (auto p = findSlotLookup(hash, key)) {
			// clear entry
			p.hash = Hash.deleted;
			// just mark it to be disposed

			++deleted;
			return true;
		}
		return false;
	}

	void clear() {
		deleted = used = 0;
		buckets[] = Bucket.init;
	}

	V* opBinaryRight(string op : "in")(in K key) {
		if (!length)
			return null;

		const keyHash = calcHash(key);
		if (auto buck = findSlotLookup(keyHash, key))
			return &buck.val;
		return null;
	}

	V get(in K key) {
		if (auto ret = key in this)
			return *ret;
		return V.init;
	}

	alias opIndex = get;

	void opIndexAssign(V value, in K key) {
		set(key, value);
	}
}

unittest {
	Map!(int, int, 4) m;
	assert(m.empty);
	assert(m.set(1, 2));
	assert(m.set(2, 3));
	assert(m.set(3, 4));
	assert(m.length == 3);
	assert(m.set(4, 5));
	assert(m.length == 4);
	assert(!m.set(5, 6));
	assert(m.length == 4);
	assert(m.remove(2));
	assert(m.length == 3);
	assert(m.set(5, 6));
	assert(m.length == 4);
	assert(m.remove(5));
	assert(m.length == 3);
}

private:
size_t mix(size_t h) @safe pure nothrow @nogc {
	enum m = 0x5bd1e995;
	h ^= h >> 13;
	h *= m;
	h ^= h >> 15;
	return h;
}

enum INIT_NUM_BUCKETS = 8;

/// magic hash constants to distinguish empty, deleted, and filled buckets
enum Hash : size_t {
	empty = 0,
	deleted = 0x1,
	filled = size_t(1) << 8 * size_t.sizeof - 1,
}
